#include<iostream>
#include<assert.h>
using namespace std;
namespace sakura1 {
	template<class T>
	struct TreeNode {
		TreeNode(T _val)
			:val(_val)
			, sign(0)
			, parent(nullptr)
			, left(nullptr)
			, right(nullptr)
		{}
		T val;
		int sign;
		TreeNode<T>* _parent;
		TreeNode<T>* left;
		TreeNode<T>* right;
	};
	template<class T>
	class AVLTree {
		typedef TreeNode<T> Node;
	public:
		void Insert(T _val)
		{
			if (root == nullptr)
			{
				root = new Node(_val);
			}
			else
			{
				Node* sakura = root;
				Node* parent = nullptr;
				while (sakura)
				{
					if (_val <= sakura->val)
					{
						parent = sakura;
						sakura = sakura->left;
					}
					else if (_val > sakura->val)
					{
						parent = sakura;
						sakura = sakura->right;
					}
				}
				sakura = new Node(_val);
				sakura->_parent = parent;
				if (_val < parent->val)
				{
					parent->left = sakura;
					parent->sign--;
				}
				if (_val > parent->val)
				{
					parent->right = sakura;
					parent->sign++;
				}
				while (parent)
				{
					Node* Pparent = parent->_parent;
					if (parent->sign == 0)
						break;
					else if (parent->sign == 1 || parent->sign == -1)
					{
						if (Pparent->left == parent)
							Pparent->sign--;
						else
							Pparent->sign++;
					}
					else if (parent->sign == 2 || parent->sign == -2)
					{
						if (parent->sign == -2 && sakura->sign == -1)
						{
							RevolveR(parent);
						}
						else if (parent->sign == 2 && sakura->sign == 1)
						{
							RevolveL(parent);
						}
						else if (parent->sign == -2 && sakura->sign == 1)
						{

						}
						else if (parent->sign == 2 && sakura->sign == -1)
						{
						}
						else
						{
							assert(false);
						}
					}
					parent = Pparent;
				}
				
			}
		}
		void RevolveR(Node*& parent)
		{
			Node* cur = parent->left;
			Node* curR = cur->right;
			if (parent == root)
			{
				cur->_parent == nullptr;
				root = cur;
			}
			else
			{
				Node* Pparent = parent->_parent;
				cur->_parent = Pparent;
				if (parent == Pparent->left)
					Pparent->left = cur;
				else
					Pparent->right = cur;
			}
			if (curR)
				curR->_parent = parent;
			parent->_parent = cur;
			cur->right = parent;
			parent->sign == cur->sign == 0;
		}
		void RevolveL(Node*& parent)
		{
			Node* cur = parent->left;
			Node* curL = cur->left;
			if (parent == root)
			{
				cur->_parent == nullptr;
				root = cur;
			}
			else
			{
				Node* Pparent = parent->_parent;
				cur->_parent = Pparent;
				if (parent == Pparent->left)
					Pparent->left = cur;
				else
					Pparent->right = cur;
			}
			if (curL)
				curL->_parent = parent;
			parent->_parent = cur;
			cur->right = parent;
			parent->sign == cur->sign == 0;
		}
	private:
		Node* root = nullptr;
	};
}
namespace sakura2 {
	template<class T, class V>
	struct TreeNode {
		TreeNode(T _val, V _value)
			:val(_val)
			, value(_value)
			, left(nullptr)
			, right(nullptr)
		{}
		T val;
		V value;
		TreeNode<T, V>* left;
		TreeNode<T, V>* right;
	};
	template<class T, class V>
	class BSTree {
		typedef TreeNode<T, V> Node;
	public:
		void Insert(T _val, V _value)
		{
			if (root == nullptr)
			{
				root = new Node(_val, _value);
			}
			else
			{
				Node* sakura = root;
				Node* parent = nullptr;
				while (sakura)
				{
					if (_val <= sakura->val)
					{
						parent = sakura;
						sakura = sakura->left;
					}
					else if (_val > sakura->val)
					{
						parent = sakura;
						sakura = sakura->right;
					}
				}
				sakura = new Node(_val, _value);
				if (_val < parent->val)
					parent->left = sakura;
				if (_val > parent->val)
					parent->right = sakura;
			}
		}
		Node* Find(T _val)
		{
			Node* sakura = root;
			while (sakura)
			{
				if (_val < sakura->val)
				{
					sakura = sakura->left;
				}
				else if (_val > sakura->val)
				{
					sakura = sakura->right;
				}
				else
					return sakura;
			}
			return nullptr;
		}
		bool Erase(T _val)
		{
			Node* parent = nullptr;
			Node* sakura = root;
			while (sakura)
			{
				if (_val < sakura->val)
				{
					parent = sakura;
					sakura = sakura->left;
				}
				else if (_val > sakura->val)
				{
					parent = sakura;
					sakura = sakura->right;
				}
				else
				{
					if (sakura->left == nullptr)
					{
						if (sakura == root)
						{
							root = root->right;
						}
						else
						{
							if (parent->left == sakura)
								parent->left = sakura->right;
							else
								parent->right = sakura->right;
						}
					}
					else if (sakura->right == nullptr)
					{
						if (sakura == root)
						{
							root = root->left;
						}
						else
						{
							if (parent->left == sakura)
								parent->left = sakura->left;
							else
								parent->right = sakura->left;
						}
					}
					else
					{
						Node* _root = sakura;
						parent = sakura;
						sakura = sakura->right;
						while (sakura->left)
						{
							parent = sakura;
							sakura = sakura->left;
						}
						_root->val = sakura->val;
						if (parent->left == sakura)
							parent->left = sakura->right;
						else
							parent->right = sakura->right;
					}
					delete sakura;
					return true;
				}
			}
			return false;
		}
		void Printf()
		{
			_Printf(root);
			cout << endl;
		}
	private:
		void _Printf(Node* root)
		{
			if (root == nullptr)
				return;
			else
			{
				_Printf(root->left);
				cout << root->val << " " << root->value << endl;
				_Printf(root->right);
			}
			return;
		}
		Node* root = nullptr;
	};
}
